package Leetcode;

public class Leetcode_42 {
        public static int fib(int n) {
            final int MOD = 1000000007;
            if (n < 2) {
                return n;
            }
            int p = 0, q = 0, r = 1;
            for (int i = 2; i <= n; ++i) {
                p = q;
                q = r;
                r = (p + q) % MOD;
            }
            return r;
        }
    public static void main(String[] args) {
       int n = 5;
       int a = fib(n);
       System.out.println(a);
    }
}
